package com.fanshuai.algorithms.greedy;

import com.fanshuai.algorithms.datastructure.graph.DirectGraph;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class MinPath {
    /**
     * 单源最短路径  dijkstra算法  贪心算法
     *
     * 设有向图G，原点为src，设置顶点集合S，从原点src到集合内顶点的最短路径已知。使用贪心策略不断扩充集合S，直到图的所有顶点
     *
     * 顶点编号为[0..n-1]，
     * join = new boolean[n] 表示是否加入到集合中
     * dist = new int[n] dist[j]记录从src到j的最短路径
     * parent = new int[n] 指向父节点的树
     *
     * 贪心策略：每次选择join[j]=false, dist[j]最小的顶点j，加入，同时更新dist数组。直到S[i]均为true, i=[0..n-1]
     * @param matrix 邻接矩阵 [1,n]
     * @param src  源点
     * @param dest 目标节点
     * @return
     */
    public static int dijkstra(int[][] matrix, int src, int dest) {
        int n = matrix.length - 1;

        boolean[] join = new boolean[n]; //是否加入集合S
        int[] dist = new int[n]; //从src到j的最短路径数组
        int[] parent = new int[n];//指向父节点的树

        join[src] = true;
        dist[src] = 0;
        parent[src] = src;
        for (int j = 0; j < n && j != src; j++) { //初始化dist
            dist[j] = matrix[src][j];
            parent[j] = -1;
        }

        int j = src;
        while (!isAllJoined(join)) {
            int min = Integer.MAX_VALUE;
            int next = -1;
            for (int i = 0; i < n; i++) {
                if (!join[i] && dist[i] < min) {
                    //寻找距离最小的相邻节点
                    min = dist[i];
                    next = i;
                }
            }

            if (next == -1) {
                break;
            } else {
                j = next; //更新下一个节点
                join[j] = true; //加入S集合

                //更新dist数组
                for (int i = 0; i < n; i++) {
                    if (!join[i] && matrix[j][i] < Integer.MAX_VALUE && dist[j] + matrix[j][i] < dist[i]) {
                        dist[i] = dist[j] + matrix[j][i];
                        parent[i] = j;
                    }
                }
            }
        }

        return dist[dest];
    }

    /**
     * 顶点是否全部加入S中
     * @param join
     * @return
     */
    private static boolean isAllJoined(boolean[] join) {
        for (int i = 1; i < join.length; i++) {
            if (!join[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        DirectGraph<Integer> graph = new DirectGraph<>(6);

        String path = System.getProperty("user.dir") + "/src/main/java/com/fanshuai/algorithms/branch/";
        List<String> lines = Files.readAllLines(Paths.get(path + "graph1"));

        for (int i = 2; i < lines.size(); i++) {
            String line = lines.get(i);
            String[] arr = line.split(" ");

            int x = Integer.valueOf(arr[0]);
            int y = Integer.valueOf(arr[1]);
            int weight = Integer.valueOf(arr[2]);
            graph.addEdge(x, y, weight);
        }
        int[][] pairs = new int[][] {{1, 2}, {1, 3}, {1, 4}, {1, 5},
                {1, 6}, {3, 4}, {3, 6}, {4, 6}};

        for (int[] pair: pairs) {
            int min = dijkstra(graph.getMatrix(), pair[0], pair[1]);
            System.out.println(String.format("min path=%d", min));
        }
    }
}
